package com.example.sorts11.sort;

/**
 * 冒泡排序
 * 冒泡排序改进
 * 插入排序
 * 选择排序
 * @auther lijiewei
 * @date 2021/8/25 14:00
 */
public class Sorts {

    /**
     * 冒泡排序
     * @param a 数组
     * @param n 数组大小
     * @return
     * @author lijiewei
     * @date   2021/8/25 14:08
     */
    public static void bubbleSort(int[] a, int n) {
        if (n <= 1) {
            return;
        }
        for (int i = 0; i < n; i++) {
            //提前退出标志位
            boolean flag = false;
            //j < n-i-1：在比较时已经将后一位a[j+1]进行了比较
            for (int j = 0; j < n-i-1; j++) {
                if (a[j] > a[j+1]) {
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                    //此次冒泡有数据交换
                    flag = true;
                }
            }
            //没有交换时，表示都有序,提前退出
            if (!flag) {
                break;
            }
        }
    }

    /**
     * 冒泡排序改进：在每一轮排序后记录最后一次元素交换的位置，作为下次比较的边界
     * 对于边界外的元素在下次循环中无需比较
     * @param a 数组
     * @param n 数组大小
     * @return
     * @author lijiewei
     * @date   2021/8/25 14:45
     */
    public static void bubbleSort2(int[] a, int n) {
        if (n <= 1) {
            return;
        }

        //无序数据的边界，每次只需要比较到这里即可退出
        int sortBorder = n-1;
        for (int i=0; i<n; i++) {
            //提前退出标志位
            boolean flag = false;
            //最后一次交换的位置
            int lastExchange = 0;
            for (int j = 0; j < sortBorder; j++) {
                if (a[j] > a[j+1]) {
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                    //此次冒泡有数据交换
                    flag = true;
                    //更新最后一次交换位置
                    lastExchange = j;
                }
            }
            sortBorder = lastExchange;
            //没有交换时，表示都有序,提前退出
            if (!flag) {
                break;
            }
        }
    }

    /**
     * 插入排序
     * @param a 数组
     * @param n 数组大小
     * @return
     * @author lijiewei
     * @date   2021/8/25 15:02
     */
    public static void insertionSort(int[] a, int n) {
        if (n <= 1) {
            return;
        }
        //i左边为已排序的
        for (int i = 1; i < n; i++) {
            int value = a[i];
            //用于和左边有序元素对比
            int j = i-1;
            for (; j>=0 ; j--) {
                if (a[j] > value) {
                    a[j+1] = a[j];
                } else {
                    break;
                }
            }
            a[j+1] = value;
        }
    }

    /**
     * 选择排序
     * @param a 数组
     * @param n 数组大小
     * @return
     * @author lijiewei
     * @date   2021/8/25 15:15
     */
    public static void selectionSort(int[] a, int n) {
        if (n <= 1) {
            return;
        }
        //i<n-1: 最后一次只有一个元素，且最大，不用执行
        for (int i = 0; i < n-1; i++) {
            //查找最小值
            int minIndex = i;
            //从 i 到 n 中选择最小的
            for (int j = i+1; j < n; j++) {
                if (a[j] < a[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = tmp;
        }
    }
}
